package com.hspedu.newData.dmsxl.树;

import com.hspedu.newData.dmsxl.ds.TreeNode;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-05-13 
 * @Version: 1.0
 */

public class LC653两数之和输入二叉搜索树 {

    List<Integer> list = new ArrayList<>();

    public boolean findTarget(TreeNode root, int k) {

        dfs(root);
        int i = 0;
        int j = list.size() - 1;

        while (i<j){
            int target = list.get(i) + list.get(j);
            if (target > k){
                j--;
            }else if (target<k){
                i++;
            }else {
                return true;
            }
        }
        return false;
    }

    public void dfs(TreeNode root){
        if (root == null){
            return;
        }

        dfs(root.left);
        list.add(root.val);
        dfs(root.right);
    }


    @Test
    public void test() {
        // 测试代码

        // 测试代码

        TreeNode t7 = new TreeNode(7);
//        TreeNode t6 = new TreeNode(6);
        TreeNode t5 = new TreeNode(4);
        TreeNode t4 = new TreeNode(2);
        TreeNode t3 = new TreeNode(6,null,t7);
        TreeNode t2 = new TreeNode(3,t4,t5);
        TreeNode t1 = new TreeNode(5,t2,t3);

        findTarget(t1,8);
        System.out.println("==========");

    }
}
